package com.kosam.leetcode.tag.sort;

import java.util.Arrays;
import java.util.HashSet;

/**
 * 给定两个数组，编写一个函数来计算它们的交集。
 * https://leetcode-cn.com/problems/intersection-of-two-arrays/
 */
public class LeetCode349 {

    /**
     * 思路1：
     * 如果按常规思路去实现，遍历两个数组去比较是否相等，时间的复杂度可能是 O( n * m)
     * 思路2：
     * 先将两个数组放入set, 然后用较少元素的去比较是否包含在较大元素集合
     * @param nums1
     * @param nums2
     * @return
     */
    private static int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set1 = new HashSet<Integer>(nums1.length);
        for (int num : nums1) set1.add(num);

        HashSet<Integer> set2 = new HashSet<Integer>(nums2.length);
        for (int num : nums2) set2.add(num);

        if (set1.size() <= set2.size()) {
            return cal_intersection(set1, set2);
        } else {
            return cal_intersection(set2, set1);
        }
    }

    private static int[] cal_intersection(HashSet<Integer> set1, HashSet<Integer> set2) {
        int[] result = new int[set1.size()];
        int resultIndex = 0;
        for (int num : set1) {
            if (set2.contains(num)) {
                result[resultIndex++] = num;
            }
        }
        return Arrays.copyOf(result, resultIndex);
    }

    public static void main(String[] args) {
        // nums1 = [4,9,5], nums2 = [9,4,9,8,4]
        int[] nums1 = new int[]{4, 9, 5};
        int[] nums2 = new int[]{9, 4, 9, 8, 4};
        System.out.println(Arrays.toString(intersection(nums1, nums2)));
    }
}
